Introduction

The methods of cluster analysis can be applied to the process of segmenting an image by assigning to each pixel a label indicating some form of shared characteristic such as boundaries or colours. The goal is to identify important regions of an image where each segment belongs to one particular surface, object, etc. There are applications in image processing/compression, object recognition, database searching, edge detection for feature extraction and so on.

The Imager package cotains some example images to work with. We will import the parrots file as it can highlight the ease with which algorithms can segment within a 3 dimensional color space (RGB).

file <- system.file('extdata/parrots.png',package='imager')
parrots <- load.image(file)
parrots
## Image. Width: 768 pix Height: 512 pix Depth: 1 Colour channels: 3

The data is stored as a cimg class, which behaves identically as an array. For purposes of plotting with the ggplot2 package, which requires data be stored as a dataframe we convert the default cmig object.

parrots_df <- as.data.frame(parrots,wide="c") %>% # wide format with channels as columns
  mutate(rgb.val=rgb(c.1,c.2,c.3)) 
names <- c("x", "y", "R", "G", "B", "rgb.val")
colnames(parrots_df) <- names
x y R G B rgb.val
1 1 0.4549020 0.4549020 0.3450980 #747458
2 1 0.4588235 0.4588235 0.3490196 #757559
3 1 0.4705882 0.4705882 0.3607843 #78785C

The image has a wide colour palette that we hope will serve as the basis of our segmentation. Without using spacial information, each pixel has a corresponding 3-dimentional vector of color channels – red, green, and blue. The K-means algorithm should perform well here since the colours help to differentiate the parrots from each other and the background (i.e. good separation).

K-Means Clustering

The K-means method is a simple solution to the problem of finding clusters centers that minimize the variance within each cluster. Each cluster in our problem refers to a specific colour value. A pixel is considered to be “like” another if they are near each other in the colour space. Euclidean distance will define the notion of “nearness”. K-means requires that we specify the number of clusters a-priori. What is the optimal number of clusters depends on the problem at hand. The goal of segmenting an image is only to find the colours that we deem most important in separating the objects. The salient colours in the parrots image are red, green, turquoise, yellow, white, and black. So we might choose the number of clusters to be around 6-8. Next, we need to choose a method of initalization for the pixel centers. The K-means++ algorithm is a seeding procedure fro the centers which results in an improvement of the final error and a decrease in computation time. Intuitively, initial centers should be chosen such that they are not too close together. This idea is implemented in the function below.

# rows are centers
centers <- function(x, k) {
  x <- as.matrix(x)
  center.mat <- matrix(0, nrow=k,ncol=ncol(x))
  center.init <- x[sample(nrow(x), size=1), ]
  center.mat[1, ] <- center.init
  for (i in 2:k) {
    e.dist <- sqrt(rowSums((x-center.init)^2)) # compute euclidean distance
    probs <- e.dist^2 / (max(e.dist)^2 + 1) # weighted probability
    center.new <- x[sample(nrow(x), size=1, prob=probs), ]
    
    center.mat[i, ] <- center.new
  }
  center.mat
}

Although this initialization process does require some computational effort, the K-means procedure should converge more quickly on average. Now we will use this in conjunction with R’s built in kmeans function.

kmpp <- function(x, k) {
  centers <- centers(x, k)
  kmeans(x, centers)
}
cl <- kmpp(parrots_df[, c("R", "G", "B")], k=8)
kColours <- rgb(cl$centers[cl$cluster, ])

Application to Medical Imaging

brain <- load.image("brain.jpg") # Read the image
brain_df <- as.data.frame(brain,wide="c")
names <- c("x", "y", "R", "G", "B")
colnames(brain_df) <- names
set.seed(105)
cl <- kmeans(brain_df[, c("R", "G", "B")], 5)
kIntensity <- rgb(cl$centers[cl$cluster, ])

 

A work by Derek Wayne

derekwayne4@gmail.com